package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * 剑指offer
 * 数组中只出现一次的两个数字
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：17955
 * 本题知识点： 位运算 哈希
 * 算法知识视频讲解
 * 题目描述
 * 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * 示例1
 * 输入
 * 复制
 * [1,4,1,6]
 * 返回值
 * 复制
 * [4,6]
 * 说明
 * 返回的结果中较小的数排在前面
 */
public class FindNumsAppearOnce {

    @Test
    public void test() {
        System.out.println(Arrays.toString(FindNumsAppearOnce(new int[]{2, 4, 3, 6, 3, 2, 5, 5})));
    }

    public int[] FindNumsAppearOnce(int[] array) {
        // 用hashmap
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                map.remove(array[i]);
            } else {
                map.put(array[i], 1);
            }
        }

        int[] result = new int[map.size()];

        int index = 0;

        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                result[index++] = array[i];
            }
        }

        return result;
    }

    // 用脚底板都能想出来的思路，没什么高级的，就是使用arraylist工具类而已：
//    public int[] FindNumsAppearOnce (int[] array) {
//        // write code here
//        ArrayList<Integer> integers = new ArrayList<>();
//
//        for (int i = 0; i < array.length; i++) {
//            if (integers.contains(array[i])) {
//                integers.remove(new Integer(array[i]));
//            } else {
//                integers.add(array[i]);
//            }
//        }
//
//        int[] result = new int[integers.size()];
//
//        for (int i = 0; i < result.length; i++) {
//            result[i] = integers.get(i);
//        }
//
//        return result;
//    }
}
